{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Take Gifts From the Richest Pile"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #simulation #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #模拟 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: pickGifts"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从数量最多的堆取走礼物"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>gifts</code> ，表示各堆礼物的数量。每一秒，你需要执行以下操作：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择礼物数量最多的那一堆。</li>\n",
    "\t<li>如果不止一堆都符合礼物数量最多，从中选择任一堆即可。</li>\n",
    "\t<li>选中的那一堆留下平方根数量的礼物（向下取整），取走其他的礼物。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回在 <code>k</code> 秒后剩下的礼物数量<em>。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>gifts = [25,64,9,4,100], k = 4\n",
    "<strong>输出：</strong>29\n",
    "<strong>解释：</strong> \n",
    "按下述方式取走礼物：\n",
    "- 在第一秒，选中最后一堆，剩下 10 个礼物。\n",
    "- 接着第二秒选中第二堆礼物，剩下 8 个礼物。\n",
    "- 然后选中第一堆礼物，剩下 5 个礼物。\n",
    "- 最后，再次选中最后一堆礼物，剩下 3 个礼物。\n",
    "最后剩下的礼物数量分别是 [5,8,9,4,3] ，所以，剩下礼物的总数量是 29 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>gifts = [1,1,1,1], k = 4\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>\n",
    "在本例中，不管选中哪一堆礼物，都必须剩下 1 个礼物。 \n",
    "也就是说，你无法获取任一堆中的礼物。 \n",
    "所以，剩下礼物的总数量是 4 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= gifts.length &lt;= 10<sup>3</sup></code></li>\n",
    "\t<li><code>1 &lt;= gifts[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>3</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [take-gifts-from-the-richest-pile](https://leetcode.cn/problems/take-gifts-from-the-richest-pile/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [take-gifts-from-the-richest-pile](https://leetcode.cn/problems/take-gifts-from-the-richest-pile/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[25,64,9,4,100]\\n4', '[1,1,1,1]\\n4']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heapify,heappop, heappush\n",
    "from math import sqrt\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        gifts = [-x for x in gifts]\n",
    "        heapify(gifts)\n",
    "        for _ in range(k):\n",
    "            num = -heappop(gifts)\n",
    "            heappush(gifts, -int(sqrt(num)))\n",
    "\n",
    "        return -sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for i in range(0, k):\n",
    "            # max_value = \n",
    "            gifts[gifts.index(max(gifts))] = int(math.sqrt(max(gifts)))\n",
    "        return sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        giftsHeap = []\n",
    "        for x in gifts:\n",
    "            heappush(giftsHeap, -x)\n",
    "        for i in range(k):\n",
    "            x = -heappop(giftsHeap)\n",
    "            heappush(giftsHeap, - (floor(sqrt(x))))\n",
    "        return -sum(giftsHeap)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        heap = [-gift for gift in gifts]\n",
    "        heapq.heapify(heap)\n",
    "\n",
    "        for i in range(k):\n",
    "            m = -heapq.heappop(heap)\n",
    "            heapq.heappush(heap, -int(m**0.5))\n",
    "        return -sum(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        g = [-x for x in gifts]\n",
    "        heapify(g)\n",
    "        for i in range(k):\n",
    "            x = -heappop(g)\n",
    "            heappush(g, -isqrt(x))\n",
    "\n",
    "        return -sum(g)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        h = [-gift for gift in gifts]\n",
    "        heapify(h)\n",
    "        while k:\n",
    "            x = heappop(h)\n",
    "            heappush(h,-int(sqrt(-x)))\n",
    "            k -= 1\n",
    "        return -sum(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for i in range(len(gifts)):\n",
    "            gifts[i] *= -1  # 变成相反数，这样堆化后就是最大堆了\n",
    "        heapify(gifts)  # 原地堆化\n",
    "        while k and -gifts[0] > 1:\n",
    "            heapreplace(gifts, -isqrt(-gifts[0]))  # 直接修改堆顶\n",
    "            k -= 1\n",
    "        return -sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        # 优先队列(最大堆)\n",
    "        q = [-gift for gift in gifts]\n",
    "        heapify(q)\n",
    "        for _ in range(k):\n",
    "            x = heappop(q)\n",
    "            heappush(q, -int(sqrt(-x)))\n",
    "        return -sum(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        h = [-v for v in gifts]\n",
    "        heapify(h)\n",
    "        for _ in range(k):\n",
    "            heapreplace(h,-int(sqrt(-h[0])))\n",
    "        return -sum(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        h = [-gift for gift in gifts]\n",
    "        heapify(h)\n",
    "        for i in range(k):\n",
    "            heapreplace(h, -int(sqrt(-nsmallest(1, h)[0])))\n",
    "        return -sum(h)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for i in range(k):\n",
    "            gifts[gifts.index(max(gifts))]=int(math.sqrt(max(gifts)))\n",
    "            \n",
    "        ans=0\n",
    "        for j in gifts:\n",
    "            ans=ans+j\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for i in range(k):\n",
    "            maxg = max(gifts)\n",
    "            gifts[gifts.index(maxg)] = int(sqrt(maxg))\n",
    "        return sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        a=0\n",
    "        c=0\n",
    "        for _ in range(k):\n",
    "            a=max(gifts)\n",
    "            b=int(math.sqrt(a))\n",
    "            gifts.remove(a)\n",
    "            gifts.append(b)\n",
    "        c=sum(gifts)\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        import heapq\n",
    "        gifts = [-x for x in gifts]\n",
    "        heapq.heapify(gifts)\n",
    "        for _ in range(k):\n",
    "            max = heapq.heappop(gifts)\n",
    "            heapq.heappush(gifts, -int((-max) ** 0.5))\n",
    "        return -sum(gifts)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        gifts.sort();\n",
    "        giftsLen = len(gifts);\n",
    "        q = deque(maxlen = giftsLen);\n",
    "        cur = 0;\n",
    "        qFront = 0;\n",
    "        arrBack = 0;      \n",
    "\n",
    "        while k > 0 :\n",
    "            k -= 1;\n",
    "            qFront = q[0] if len(q) > 0 else qFront;\n",
    "            arrBack = gifts[giftsLen - 1] if (giftsLen - 1 > -1) else 0;\n",
    "            if (cur >= qFront and cur >= arrBack):               \n",
    "                cur = floor(sqrt(cur));\n",
    "            elif (arrBack >= cur and arrBack >= qFront):\n",
    "                if (cur > 0):\n",
    "                    q.append(cur);\n",
    "\n",
    "                cur = arrBack;\n",
    "                cur = floor(sqrt(cur));\n",
    "                giftsLen -= 1;\n",
    "            elif (qFront >= cur and qFront >= arrBack):\n",
    "                q.append(cur);\n",
    "                cur = q.popleft();\n",
    "                cur = floor(sqrt(cur));\n",
    "\n",
    "        sum = 0;\n",
    "        for i in range(giftsLen):\n",
    "            sum += gifts[i];\n",
    "\n",
    "        while len(q) > 0:\n",
    "            sum += q.popleft();\n",
    "\n",
    "        sum += cur;\n",
    "        return sum;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for _ in range(k):\n",
    "            m = max(gifts)\n",
    "            idx = gifts.index(m)\n",
    "            gifts[idx] = isqrt(m)\n",
    "        return sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        q = [-gift for gift in gifts]\n",
    "        heapify(q)\n",
    "        while k:\n",
    "            x = heappop(q)\n",
    "            heappush(q, -int(sqrt(-x)))\n",
    "            k -= 1\n",
    "        return -sum(q)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        res = 0\n",
    "        max_value = 0\n",
    "        for i in range(0, k):\n",
    "            for j in range(0, len(gifts)):\n",
    "                if gifts[j] >= gifts[max_value]:\n",
    "                    max_value = j\n",
    "            gifts[max_value] = math.floor(math.sqrt(gifts[max_value]))\n",
    "        for i in gifts:\n",
    "            res += i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        q = [-gift for gift in gifts]\n",
    "        heapify(q)\n",
    "        while k:\n",
    "            x = heappop(q)\n",
    "            heappush(q, -int(sqrt(-x)))\n",
    "            k -= 1\n",
    "        return -sum(q)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for i in range(len(gifts)):\n",
    "            gifts[i] *= -1\n",
    "        heapify(gifts)\n",
    "        while k and -gifts[0] > 1:\n",
    "            heapreplace(gifts, -isqrt(-gifts[0]))\n",
    "            k -= 1\n",
    "        return -sum(gifts)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        # dic=defaultdict()\n",
    "        # for i in range(len(gifts)):\n",
    "        #     dic[i]=gifts[i]\n",
    "        # ans=0\n",
    "        # for i in range(k):\n",
    "        #     n=max(dic,key=dic.get)\n",
    "        #     dic[n]=int(math.sqrt(dic[n]))\n",
    "        # return sum(i for i in dic.values())\n",
    "        gifts = [-g for g in gifts]\n",
    "        heapq.heapify(gifts)\n",
    "        for i in range(k):\n",
    "            top =-heapq.heappop(gifts)\n",
    "            # top *= -1\n",
    "            top = int(math.sqrt(top))\n",
    "            heapq.heappush(gifts, -top)\n",
    "        return -sum(gifts)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        res = []\n",
    "        for gift in gifts:\n",
    "            heapq.heappush(res, -gift)\n",
    "        for _ in range(k):\n",
    "            k = -heapq.heappop(res)\n",
    "            heapq.heappush(res, -int(k**0.5))\n",
    "        return -sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        #优先队列\n",
    "        import heapq\n",
    "        #把礼物列表转换成优先队列,大小颠倒这存\n",
    "        gifts = [-_g for _g in gifts]\n",
    "        heapq.heapify(gifts)\n",
    "        for i in range(k):\n",
    "            maxGift = heapq.heappop(gifts)\n",
    "            sqrMaxGift = (-maxGift) ** 0.5\n",
    "            heapq.heappush(gifts, int(-sqrMaxGift)) \n",
    "\n",
    "        return - sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for i in range(k):\n",
    "            gifts[gifts.index(max(gifts))] = int(math.sqrt(max(gifts)))\n",
    "        return sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "       \n",
    "        \n",
    "       \n",
    "        while k > 0:\n",
    "            gifts.sort()\n",
    "            if gifts[-1] == 1:\n",
    "                break\n",
    "            gifts[-1] = floor(sqrt(gifts[-1]))     \n",
    "            \n",
    "            k -= 1\n",
    "                    \n",
    "        return sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        n = len(gifts)\n",
    "        while k:\n",
    "            gifts.sort()\n",
    "            gifts[n-1]  = int(sqrt(gifts[n-1]))\n",
    "            k -= 1\n",
    "        \n",
    "        return sum(gifts[i] for i in range(len(gifts)))\n",
    "    \n",
    "\n",
    "\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        import math\n",
    "        for i in range(k):\n",
    "            y=max(gifts)\n",
    "            x=math.floor(math.sqrt(max(gifts)))\n",
    "            gifts[gifts.index(y)]=x\n",
    "        return sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for i in range(k):\n",
    "            tmp = max(gifts)\n",
    "            tmp_index = gifts.index(tmp)\n",
    "\n",
    "            gifts[tmp_index] = floor(tmp ** 0.5)\n",
    "        \n",
    "        return sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        gift=[-i for i in gifts]\n",
    "        heapify(gift)\n",
    "        for i in range(k):\n",
    "            temp=heappop(gift)\n",
    "            #print(temp)\n",
    "            heappush(gift,-int(sqrt(-temp)))\n",
    "        return -sum(gift)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for i in range(k):\n",
    "            idx = gifts.index(max(gifts))\n",
    "            gifts[idx] = math.floor(math.sqrt(gifts[idx]))\n",
    "        \n",
    "        return sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for i in range(k):\n",
    "            gifts[gifts.index(max(gifts))] = math.floor(max(gifts) ** 0.5)\n",
    "        return sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for i in range(k):\n",
    "            gifts = sorted(gifts)\n",
    "            gifts[-1] = math.floor(math.sqrt(gifts[-1]))\n",
    "        \n",
    "        return sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for i in range(len(gifts)):\n",
    "            gifts[i] *= -1  # 变成相反数，这样堆化后就是最大堆了\n",
    "        heapify(gifts)  # 原地堆化\n",
    "        while k and -gifts[0] > 1:\n",
    "            heapreplace(gifts, -isqrt(-gifts[0]))  # 直接修改堆顶\n",
    "            k -= 1\n",
    "        return -sum(gifts)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for i in range(k):\n",
    "            maxvalue = max(gifts)\n",
    "            maxindx = gifts.index(maxvalue)\n",
    "            ss = math.sqrt(maxvalue)\n",
    "            gifts[maxindx] = int(ss)\n",
    "        return sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for i in range(k):\n",
    "            idx = gifts.index(max(gifts))\n",
    "            gifts[idx] = math.floor(math.sqrt(gifts[idx]))\n",
    "        \n",
    "        return sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        i = 0\n",
    "        while i < k:\n",
    "            max_num = max(gifts)\n",
    "            if max_num == 1:\n",
    "                break\n",
    "            remain = math.sqrt(max_num)\n",
    "            if remain == 1:\n",
    "                gifts.remove(gifts.index(max_num))\n",
    "            else:\n",
    "                gifts[gifts.index(max_num)] = int(remain)\n",
    "            i += 1\n",
    "        return sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        pq = [-x for x in gifts]\n",
    "        heapq.heapify(pq)\n",
    "        while k > 0:\n",
    "            k -= 1\n",
    "            t = -heapq.heappop(pq)\n",
    "            heapq.heappush(pq, -int(sqrt(t)))\n",
    "        return -sum(pq)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        # 25 64 9 4 10\n",
    "        # 25 8 9 4 10\n",
    "        # 5 8 9 4 10\n",
    "        # 5 8 9 4 3\n",
    "\n",
    "        q = [-gift for gift in gifts]\n",
    "        heapify(q)\n",
    "        while k:\n",
    "            x = heappop(q)\n",
    "            heappush(q, -int(sqrt(-x)))\n",
    "            k -= 1\n",
    "        return -sum(q)\n",
    "\n",
    "\n",
    "# 答案 - leetcode官方题解\n",
    "# https://leetcode.cn/problems/take-gifts-from-the-richest-pile/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        import heapq\n",
    "        for i in range(0, len(gifts)):\n",
    "            gifts[i] = -gifts[i]\n",
    "        heapq.heapify(gifts)\n",
    "        for _ in range(k):\n",
    "            heapq.heappushpop(gifts, -(int((-gifts[0])**0.5)))\n",
    "        return -sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        gifts.sort()\n",
    "        n = len(gifts)\n",
    "        res = sum(gifts)\n",
    "        while k > 0:\n",
    "            temp = int(gifts[-1] ** 0.5)\n",
    "            res -= gifts[-1] - temp\n",
    "            gifts[-1] = temp\n",
    "            gifts.sort()\n",
    "            # j = n - 2\n",
    "            # while j >= 0 and gifts[j] > temp:\n",
    "            #     gifts[j+1] = gifts[j]\n",
    "            #     j -= 1\n",
    "            # gifts[j+1] = temp\n",
    "\n",
    "            k -= 1\n",
    "\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        gifts.sort()\n",
    "        n = len(gifts)\n",
    "        res = sum(gifts)\n",
    "        while k > 0:\n",
    "            temp = int(gifts[-1] ** 0.5)\n",
    "            j = n - 2\n",
    "            while j >= 0 and gifts[j] > temp:\n",
    "                gifts[j+1] = gifts[j]\n",
    "                j -= 1\n",
    "            gifts[j+1] = temp\n",
    "\n",
    "            k -= 1\n",
    "        return sum(gifts)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "       \n",
    "     \n",
    "        while k > 0:\n",
    "            max1 = max(gifts)\n",
    "            \n",
    "            for j in range(len(gifts)):\n",
    "                if gifts[j] == max1:\n",
    "                    gifts[j] = floor(sqrt(gifts[j]))\n",
    "                    break\n",
    "            k -= 1\n",
    "                    \n",
    "        return sum(gifts)\n",
    "                  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        # 将所有礼物堆的数量变为负数并存入堆中\n",
    "        gifts = [-gift for gift in gifts]\n",
    "        heapq.heapify(gifts)\n",
    "\n",
    "        for _ in range(k):\n",
    "            # 每次都取出数量最多的礼物堆\n",
    "            max_gifts = -heapq.heappop(gifts)\n",
    "            # 计算取走礼物后剩下的礼物数量\n",
    "            left_gifts = int(math.sqrt(max_gifts))\n",
    "            # 将剩下的礼物数量（负数）放回堆中\n",
    "            heapq.heappush(gifts, -left_gifts)\n",
    "\n",
    "        # 计算 k 秒后剩下的总礼物数量\n",
    "        total_gifts_left = -sum(gifts)\n",
    "        return total_gifts_left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        gifts = [-x for x in gifts]\n",
    "        heapq.heapify(gifts)\n",
    "        while k > 0:\n",
    "            n = -heapq.heappop(gifts)\n",
    "            n = -int(math.sqrt(n))\n",
    "            heapq.heappush(gifts, n)\n",
    "            k -= 1\n",
    "        return -sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        while k:\n",
    "            n=max(gifts)\n",
    "            m=gifts.index(n)\n",
    "            gifts[m]=int(sqrt(n))\n",
    "            k-=1\n",
    "        return sum(gifts)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        heap = []\n",
    "        for i in gifts:\n",
    "            heapq.heappush(heap,-i)\n",
    "        for i in range(k):\n",
    "            heapq.heappush(heap,-int(math.sqrt(-heapq.heappop(heap))))\n",
    "        return -sum(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        gifts.sort()\n",
    "        for _ in range(k):\n",
    "            new=floor(sqrt(gifts[-1]))\n",
    "            i=0\n",
    "            j=len(gifts)-1\n",
    "            while i<=j:\n",
    "                mid=(i+j)//2\n",
    "                if gifts[mid]<new:\n",
    "                    i=mid+1\n",
    "                else:\n",
    "                    j=mid-1\n",
    "            gifts.insert(i,new)\n",
    "            gifts.pop(-1)\n",
    "        return sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        x = [-g for g in gifts]\n",
    "        heapify(x)\n",
    "        while k:\n",
    "            val = int(sqrt(abs(heappop(x))))\n",
    "            heappush(x, -val)\n",
    "            k -= 1\n",
    "        return -sum(x)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findmax(self, nums: List[int]) -> int:\n",
    "        max_n = 0\n",
    "        max_i = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] > max_n:\n",
    "                max_n = nums[i]\n",
    "                max_i = i\n",
    "        return max_i\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for i in range(k):\n",
    "            max_i = self.findmax(gifts)\n",
    "            gifts[max_i] = int(sqrt(gifts[max_i]))\n",
    "        s = sum(gifts)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for count in range(k):\n",
    "            maxs=max(gifts)\n",
    "            num=math.floor(math.sqrt(maxs))\n",
    "            gifts.remove(maxs)\n",
    "            gifts.append(num)\n",
    "        return sum(gifts)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import*\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for _ in range(k):\n",
    "            i=gifts.index(max(gifts))\n",
    "            gifts[i]=int(sqrt(gifts[i]))\n",
    "        return sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        q = [-gift for gift in gifts]\n",
    "        heapify(q)\n",
    "        while k:\n",
    "            x = heappop(q)\n",
    "            heappush(q, -int(sqrt(-x)))\n",
    "            k -= 1\n",
    "        return -sum(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "       \n",
    "     \n",
    "        while k > 0:\n",
    "            max1 = max(gifts)\n",
    "            \n",
    "            for j in range(len(gifts)):\n",
    "                if gifts[j] == max1:\n",
    "                    gifts[j] = floor(sqrt(gifts[j]))\n",
    "                    break\n",
    "            k -= 1\n",
    "                    \n",
    "        return sum(gifts)\n",
    "                  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        q = [-g for g in gifts]\n",
    "        heapify(q)\n",
    "        while k:\n",
    "            x = heappop(q)\n",
    "            heappush(q, -int(sqrt(-x)))\n",
    "            k -= 1\n",
    "        return -sum(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for i in range(len(gifts)):\n",
    "            gifts[i] *= -1  # 变成相反数，这样堆化后就是最大堆了\n",
    "        heapify(gifts)  # 原地堆化\n",
    "        while k and -gifts[0] > 1:\n",
    "            heapreplace(gifts, -isqrt(-gifts[0]))  # 直接修改堆顶\n",
    "            k -= 1\n",
    "        return -sum(gifts)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for _ in range(k):\n",
    "            gifts.sort(reverse=True)\n",
    "            gifts[0] = int(sqrt(gifts[0]))\n",
    "        return sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        n=len(gifts)\n",
    "        for i in range(k):\n",
    "            m=0\n",
    "            for i in range(1,n):\n",
    "                if gifts[i]>gifts[m]:\n",
    "                    m=i\n",
    "            gifts[m]=int(gifts[m]**(1/2))\n",
    "        s=0\n",
    "        for i in gifts:\n",
    "            s+=i\n",
    "        return s\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for i in range(len(gifts)):\n",
    "            gifts[i] *= -1  # 变成相反数，这样堆化后就是最大堆了\n",
    "        heapify(gifts)  # 原地堆化\n",
    "        while k and -gifts[0] > 1:\n",
    "            heapreplace(gifts, -isqrt(-gifts[0]))  # 直接修改堆顶\n",
    "            k -= 1\n",
    "        return -sum(gifts)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        def findMAX(lst):\n",
    "            ln = len(lst)\n",
    "            a, m = 0, 0\n",
    "            for i in range(ln):\n",
    "                if lst[i] > m:\n",
    "                    m = lst[i]\n",
    "                    a = i\n",
    "            return a, m\n",
    "\n",
    "        for _ in range(k):\n",
    "            j, s = findMAX(gifts)\n",
    "            gifts[j] = int(sqrt(s))\n",
    "        return sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        q = [-gift for gift in gifts]\n",
    "        heapify(q)\n",
    "        while k:\n",
    "            x = heappop(q)\n",
    "            heappush(q, -int(sqrt(-x)))\n",
    "            k -= 1\n",
    "        return -sum(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for i in range(k):\n",
    "            gifts.sort(reverse= True)\n",
    "            gifts[0]= int(sqrt(gifts[0]))\n",
    "        return sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for _ in range(k):\n",
    "            m = max(gifts)\n",
    "            gifts[gifts.index(m)] = int(sqrt(m))\n",
    "        return sum(gifts)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        q = []\n",
    "        for gift in gifts:\n",
    "            heapq.heappush(q, -gift)\n",
    "        for i in range(k):\n",
    "            max_v = -heapq.heappop(q)\n",
    "            heapq.heappush(q, -math.floor(max_v**0.5))\n",
    "        return -sum(q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        h = []\n",
    "        sum1 = 0\n",
    "        for g in gifts:\n",
    "            heappush(h, -g)\n",
    "            sum1 += g\n",
    "        for _ in range(k):\n",
    "            g = -heappop(h)\n",
    "            heappush(h, -int(g ** 0.5))\n",
    "            sum1 -= g - int(g ** 0.5)\n",
    "        return sum1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        q = [-x for x in gifts]\n",
    "        heapify(q)\n",
    "        ans = 0\n",
    "        while k > 0:\n",
    "            k -= 1\n",
    "            tp = -heappop(q)\n",
    "            heappush(q, -int(sqrt(tp)))\n",
    "        return -sum(q)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        heap = [-x for x in gifts]\n",
    "        heapify(heap)\n",
    "        for _ in range(k):\n",
    "            heappush(heap, -(floor(sqrt(-heappop(heap)))))\n",
    "        return -sum(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        q = [-g for g in gifts]\n",
    "        heapq.heapify(q)\n",
    "        for i in range(k):\n",
    "            top = heapq.heappop(q)\n",
    "            top *= -1\n",
    "            top = int(math.sqrt(top))\n",
    "            heapq.heappush(q, -top)\n",
    "        return sum([-x for x in q])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "          for i in range(len(gifts)):\n",
    "            gifts[i] *= -1 \n",
    "          heapify(gifts)\n",
    "          while k:\n",
    "            x=heappop(gifts)\n",
    "            heappush(gifts,-int(sqrt(-x)))\n",
    "            k-= 1\n",
    "          return -sum(gifts)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        n = len(gifts)\n",
    "        heap = [-x for x in gifts]\n",
    "        heapq.heapify(heap)\n",
    "        while k:\n",
    "            x = heapq.heappop(heap)\n",
    "            heapq.heappush(heap, -math.isqrt(-x))\n",
    "            k -= 1\n",
    "        return sum([-x for x in heap])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        dic=defaultdict()\n",
    "        for i in range(len(gifts)):\n",
    "            dic[i]=gifts[i]\n",
    "        ans=0\n",
    "        while k:\n",
    "            i=max(dic,key=dic.get)\n",
    "            dic[i]=floor(sqrt(dic[i]))\n",
    "            k-=1\n",
    "        return sum(i for i in dic.values())\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for i in range(k):\n",
    "            gifts.sort(reverse=-1)\n",
    "            gifts[0]=floor(sqrt(gifts[0]))\n",
    "        return sum(gifts)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        for i in range(k):\n",
    "            gifts[gifts.index(max(gifts))]=math.floor(math.sqrt(gifts[gifts.index(max(gifts))]))\n",
    "        return(sum(gifts))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        n = len(gifts)\n",
    "        for i in range(n):\n",
    "            gifts[i] *= -1\n",
    "        heapify(gifts)  # 用这个方法创建的堆是最小堆，通过加负号将最大值变为最小值，这样堆顶的值的相反数就是最大值\n",
    "        while k and -gifts[0] > 1:\n",
    "            heapreplace(gifts, -isqrt(-gifts[0]))  # 将堆顶元素进行替换，并可以重新调整堆，满足最大堆的要求\n",
    "            k -= 1\n",
    "\n",
    "        return -sum(gifts)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        heap=[-x for x in gifts]\n",
    "        heapq.heapify(heap)\n",
    "        for i in range(k):\n",
    "            a=heapq.heappop(heap)\n",
    "            heapq.heappush(heap,-int(sqrt(-a)))\n",
    "        return -sum(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "\n",
    "        class node:\n",
    "            def __init__(self, num):\n",
    "                self.num = num \n",
    "            def __lt__(self, other):\n",
    "                return self.num < other.num\n",
    "\n",
    "        q = [node(-x) for x in gifts ]\n",
    "        heapq.heapify(q)\n",
    "        for i in range(k):\n",
    "            t = heapq.heappop(q)\n",
    "            t = int(sqrt(-t.num))\n",
    "            heapq.heappush(q, node(-t))\n",
    "        #print(q)\n",
    "        return -1*sum(x.num for x in q)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        sl = SortedList(gifts)\n",
    "        for _ in range(k): sl.add(isqrt(sl.pop()))\n",
    "        return sum(sl)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def pickGifts(self, gifts: List[int], k: int) -> int:\n",
    "        n = len(gifts)\n",
    "        nums = []\n",
    "        for g in gifts:\n",
    "            nums.append(-g)\n",
    "        heapq.heapify(nums)\n",
    "\n",
    "        for _ in range(k):\n",
    "            g = -heapq.heappop(nums)\n",
    "            g_sqrt = int(math.sqrt(g))\n",
    "            heapq.heappush(nums, -g_sqrt)\n",
    "\n",
    "        return -sum(nums)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
